Гливка Антон Георгиевич

ВВЕДЕНИЕ

1. АКТУАЛЬНОСТЬ ТЕМЫ

2. СВЯЗЬ РАБОТЫ С НАУЧНЫМИ ПРОГРАММАМИ, ПЛАНАМИ, ТЕМАМИ

3. ЦЕЛЬ И ЗАДАЧИ РАЗРАБОКИ И ИССЛЕДОВАНИЯ

4. ПРЕДПОЛОГАЕМАЯ НАУЧНАЯ НОВИЗНА

5. ПРАКТИЧЕСКОЕ ЗНАЧЕНИЕ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ

6. АПРОБАЦИЯ РАБОТЫ

7. ОБЗОР ИССЛЕДОВАНИЙ И РАЗРАБОТОК ПО ТЕМЕ

8. ОПИСАНИЕ РАЗРАБАТЫВАЕМОЙ ПОДСИСТЕМЫ

9. МЕТОДЫ И СРЕДСТВА ИССЛЕДОВАНИЯ И РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

10. ОПИСАНИЕ ПОЛУЧЕННЫХ И ПЛАНИРУЕМЫХ РЕЗУЛЬТАТОВ

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

*Важное замечание

Современное промышленное предприятие представляет собой сложную многоуровневую систему. Модуль планирования производства в системах планирования и управления предприятием строится на основе математических моделей процессов на предприятии, от точности которых зависит оптимальность разрабатываемых объемно-календарных планов.

Одним из важнейших методов исследования и построения системы управления промышленным предприятием является моделирование. Современная система управления заводом не может быть представлена без использования моделей как количественного основания принятия решения при организации, планировании и регулировании производства.

Под моделью понимается мысленно или материально созданная конструкция, воспроизводящая основные, наиболее существенные черты данного экономического явления. Модель отображает величины, определяющие характеристику данного хозяйственного процесса, воспроизводит его основные признаки и связи. Она не является полным описанием реальной экономической жизни во всей ее сложности, в ней опущены второстепенные, побочные элементы и свойства, не оказывающие на результат процесса существенного влияния.

Модели могут быть представлены графически, например, график функции двух переменных или сетевая модель управления сложным комплексом работ; в виде числовых моделей-матриц, таблиц численных значений переменных и их коэффициентов, аналитических выражений математических уравнений и др.

Независимо от вида модели, моделирование экономического процесса построено на представлении его в математическом виде. Математическая модель воспроизводит в количественной форме в виде соотношений (уравнений, неравенств, тождеств) качественные закономерности, существенные взаимосвязи хозяйственной деятельности.

>> содержание

Особую значимость имеет задача оперативно-календарного планирования, которая в значительной мере влияет на результаты работы предприятия в целом.

Для предприятий дискретного типа производства характерно позаказное планирование в условиях большого разнообразия номенклатуры выпускаемой продукции и технологических операций. Все это значительно усложняет задачу оперативного календарного планирования на таких предприятиях.

Высокая размерность данной задачи и стохастичность характеристик затрудняет использование детерминированных методов для ее решения, а методы, основанные на эвристиках, не всегда позволяют получить достаточно хорошие решения.

Большинство разработанных к настоящему времени методик оперативно-календарного планирования основано на упрощенных моделях задачи, что снижает их практическую значимость, либо эти методики применимы лишь для определенных специфичных условий.

Значительную сложность, кроме того, представляет проблема оценки качества получаемых расписаний.

Таким образом, существует необходимость в разработке методики оперативного календарного планирования работы предприятий дискретного производства, которая позволила бы проводить оптимизацию расписания выпуска продукции по нескольким критериям качества с учетом существующих ограничений, формировать сменно-суточные задания подразделениям цеха и при этом обеспечивала бы получение оптимальных или близких к оптимальным решений.

>> содержание

Квалификационная работа магистра выполнялась на протяжении 2008-2009 гг. в соответствии с научными направлениями кафедры «Автоматизированные системы управления» Донецкого национального технического университета.

>> содержание

Цель работы

Целью работы является теоретическое обоснование и разработка моделей и методов для повышение эффективности работы машиностроительного предприятия за счет составления субоптимальных расписаний работы на двух уровнях – на уровне производства и на уровне цеха, на основании выбранных критериев оптимизации.

Идея работы

Путем использования современных методов обработки и интеллектуального анализа данных, создать компьютерную подсистему, которая сможет оперативно реагировать на изменение обстановки в производстве (поломка оборудования, недостача материала …), в следствии чего изменять (создавать) план, который будет оптимальным в данной ситуации.

Это позволит на практике быстро и эффективно решать задачи оперативно-производственного планирования. Разработанный программный модуль позволит сократить затрату материальных и временных ресурсов на выполнение планирования производственного процесса, повысит качество обработки информации и качество результата обработки, исключив ошибки, связанные с человеческим фактором.

Основные задачи разработки и исследований

Для реализации идеи и достижения цели магистерской работы поставлены следующие задачи:

     - проанализировать методические и теоретические материалы по математическим моделям машиностроительного производства;

     - анализ существующих методов искусственного интеллекта, используемых для оперативного планирования; сравнение методов и выбор наилучшего, позволяющего получить оптимальное расписание производственных работ;

     - проанализировать системы обработки данных и выбрать инструментарий для достижения поставленной цели магистерской работы;

     - выполнить анализ критериев и методов оперативного планирования производства на машиностроительном предприятии;

     - разработать программу для получения субоптимальных расписаний, руководствуясь изученными теоретическими сведениями.

     - экспериментальное опробование программного модуля на реальных данных.

Предмет разработки и исследований

Предметом разработки и исследования является компьютерная подсистема для оптимизации оперативного планирования производства в машиностроении, которая позволит реагировать на любые изменения в процессе производства и оперативно составлять расписания работы на производственных участках.

Объект разработки и исследований

Объектом исследования в данной работе будет процесс оперативного планирования выпуска продукции в условиях АО «НОРД».

Методология и методы исследований

Методологическую основу исследования составили положения системного анализа, методы планирования производственной программы предприятия, экономико-математические методы и модели, экспертные методы, методы принятия управленческих решений. Для разработки компьютерной подсистемы оперативного планирования производства в машиностроении выбран муравьиный алгоритм, который дает наиболее хорошие результаты по сравнению с другими инновационными методами, и генетические алгоритмы, адекватно учитывающие основные закономерности производства и реализации продукции на основе процессов естественного отбора.

>> содержание

До последнего десятилетия прошлого века в построении систем управления доминировал традиционный подход: линейные, нелинейные, адаптивные методы и др. Однако такой подход не всегда позволяет осуществлять робастное управление сложными нестационарными объектами. Данное обстоятельство послужило развитию нового научного направления – интеллектуальных систем управления.

Интеллектуальные системы управления – это системы управления, способные к “пониманию” и обучению в отношении объекта управления, возмущений, внешней среды и условий работы. Основное отличие интеллектуальных систем – наличие механизма системной обработки знаний. Главная архитектурная особенность, которая отличает интеллектуальные системы управления от традиционных, - это механизм получения, хранения и обработки знаний для реализации своих функций.

Существует несколько современных технологий, позволяющих создавать системы управления такого типа: экспертные системы, искусственные нейронные сети, нечеткая логика, генетические алгоритмы и ряд других. Интеллектуальные технологии между собой различает прежде всего то, что именно положено в основу концепции интеллектуальности – либо умение работать с формализованными знаниями человека (экспертные системы, нечеткая логика), либо свойственные человеку приемы обучения и мышления (искусственные нейронные сети и генетические алгоритмы).

Сегодня никто не отрицает, что новый подход к оптимизации, такой как муравьиный алгоритм, является очень перспективным в решении NP-трудных задач. С другой стороны генетический алгоритм высоко эффективен при решении задач глобальной оптимизации. Таким образом, интригующим представляется само сочетание генетического алгоритма и муравьиного алгоритма. Это сочетание позволит создать алгоритм решающий задачу оптимизации значительно лучше, чем эти же методы по отдельности.

Поэтому целью работы является реализация программного модуля на основе методов искусственного интеллекта, позволяющего эффективно выполнять оперативное календарное планирование на двух уровнях, на уровне предприятия и на цеховом уровне.

>> содержание

Практическая значимость полученных результатов заключается в разработке подсистемы оперативно-производственного планирования производства. Разработанный программный модуль позволит сократить затрату материальных и временных ресурсов на выполнение планирования производственного процесса, повысит качество обработки информации и качество результата обработки, исключив ошибки, связанные с человеческим фактором.

>> содержание

Апробация работы планируется на сентябрь 2009 года, во время прохождения преддипломной практики, непосредственно на машиностроительном предприятии (АО «НОРД»). Будут произведены экспериментальные исследования, на основании которых будут выбраны критерии алгоритмов оптимизации, которые будут давать лучшие результаты.

>> содержание

На локальном уровне (в пределах ДонНТУ) портал магистров может предоставить информацию о 3х работах на подобную тему, подход которых абсолютно разный. Также этой проблемой занимаются профессор кафедры АСУ, д.т.н. Лаздынь С.В. и доцент кафедры АСУ, к.т.н. Секирин А.И.

На глобальном уровне, проблема оперативного планирования производства решается. Создан ряд программных продуктов, которые можно отнести к ERP системам, но алгоритм работы этих систем имеет ряд недостатков, оптимизация работы, на данный момент, не осуществляется, системы просто используют знания о производственном процессе и просчитывают модель производства.

Основные недостатки этих систем:

     - высокая стоимость покупки;

     - проблемы внедрения из-за несоответствия конфигурации систем с поставленной задачей;

     - затруднения сопровождения продукта в связи с территориальной отдаленностью.

>> содержание

Оперативное планирование представляет собой осуществление текущей деятельности планово-экономических служб в течение короткого периода, например, разработка месячной производственной программы, составление квартальных бюджетов предприятия, контроль и корректировка полученных результатов и т.п.[1]

Оперативное планирование производства является завершающим звеном плановой работы на предприятии – продолжением и конкретизацией заданий техпромфинплана. Оно заключается в разработке на основе годовых (квартальных) планов конкретных производственных заданий на короткие промежутки времени как для предприятия в целом, так и для его подразделений и в оперативном регулировании хода производства по данным оперативного учета и контроля.[2]

Особенностью этого вида планирования является сочетание разработки плановых заданий с организацией их выполнения.[1]

В объем работ по оперативному планированию входит:

     - разработка прогрессивных календарно-плановых нормативов движения производства;

     - составление оперативных планов и графиков для цехов, участков, бригад и рабочих мест и их доведение до непосредственных исполнителей;

     - оперативный учет и контроль хода производства, предупреждение и выявление отклонений от предусмотренных планов и графиков и обеспечение стабилизации хода производства.

Календарное планирование включает распределение годовых плановых заданий по производственным подразделениям и срокам выполнения, а также доведение установленных показателей до конкретных исполнителей работ. С его помощью разрабатываются сменно-суточные задания, и согласуется последовательность выполнения работ отдельными исполнителями.

При реализации разработанного календарного плана ведется оперативный учет хода его выполнения – осуществляется сбор информации о фактическом выполнении плана, ее переработка и передача соответствующим службам предприятия.

Оперативное планирование производства по месту его выполнения делится на межцеховое и внутрицеховое.[2]

Межцеховое планирование обеспечивает разработку, регулирование и контроль выполнения планов производства и продажи продукции всеми цехами предприятия, а также координирует работу основных, проектно-технологических, планово-экономических и других функциональных служб.

На машиностроительных предприятиях, как правило, производственные программы разрабатываются и выдаются цехам плановыми службами на очередной год с квартальной и месячной разбивкой.

Содержанием внутрицехового планирования является разработка оперативных планов и составление текущих графиков работы производственных участков, поточных линий и отдельных рабочих мест на основе годовых планов производства и продажи продукции основных цехов предприятия.

В современном производстве широко распространены различные системы оперативного планирования, определяемые как внутрифирменными факторами, так и внешними рыночными условиями.

Под системой оперативного планирования производства в экономически литературе принято понимать совокупность различных методик технологий плановой работы, характеризующихся степенью централизации, объектом регулирования, составом календарно-плановых показателей, порядком учета и движения продукции и оформлена учетной документацией.[3]

Оперативное планирование производства заключается в разработке важнейших объемных календарных показателей производственно-хозяйственной деятельности предприятия. Всякий процесс оперативного планирования предусматривает выполнение экономистами-менеджерами таких этапов деятельности, как выбор стратегии развития предприятия, обоснование формы организации производства, определение логистической схемы движения материальных потоков, разработка основных календарно-плановых нормативов, оперативное планирование работы производственных подразделений организационная подготовка производства, непосредственная организация оперативной работы, текущий контроль и регулирование хода производства.

В оперативном планировании производства в зависимости от разрабатываемых показателей применяются такие основные методы, как объемный, календарный, а также их разновидности: объемно-календарный и объемно-динамический.[4]

Можно сделать вывод, что оперативное планирование производства, как свидетельствует передовой опыт, играет главную роль в обеспечении своевременного выпуска и поставки продукции потребителям на основе рационального использования ограниченных экономических ресурсов в текущем периоде времени. Дальнейшее развитие оперативного планирования на отечественных предприятиях будет способствовать решению следующих организационно-экономических задач:

     - достижение согласованной работы всех звеньев производства на основе единой рыночной цели, предусматривающей равномерный выпуск и сбыт товаров;

     - совершенствование всей системы внутрифирменного планирования за счет повышения надежности календарно-плановых расчетов и снижения трудоемкости;

     - повышение гибкости и оперативности внутрихозяйственного планирования на основе более полного учета требований потребителей и последующей корректировки годовых планов;

     - обеспечение непрерывности в процессе производственного планирования и достижение более тесного взаимодействия стратегических, тактических и оперативных планов;

     - создание на каждом предприятии системы оперативного планирования производства, соответствующей современным требованиям рынка и уровню развития конкретного предприятия.

Совершенствование оперативно-производственного планирования на отечественных предприятиях будет способствовать подъему производства и росту эффективности в условиях действующих рыночных отношений.

Таким образом, можно сказать, что основная задача оперативного планирования сводится в конечном итоге к обеспечению на предприятии слаженного и ритмического хода всех производственных процессов с целью наибольшего удовлетворения основных потребностей рынка, рационального использования имеющихся экономических ресурсов и максимизации получаемой прибыли.[2]

Задачу оперативного планирования производства можно разбить на несколько подзадач, очередность и зависимость которых показана на рисунке 8.1.

Рисунок 8.1 – Иерархия оперативного планирования производства

На рисунке 8.1 представлена очередность операций при формировании оперативных планов производства.

Как видно из рисунка планово-экономический отдел должен передать в подсистему оперативного планирования производства данные о заказах за квартал. Далее необходимо распределить задания таким образом, чтобы выполнить условия по договорам с заказчиками точно в срок, либо с минимальной задержкой, при этом необходимо точно составить график сборки изделий на месяц (количество изделий и сроки выпуска), чтобы собрать готовую продукцию для разных заказов в полном объеме. Из графика сборки вытекает потребность в деталях и узлах, для изготовления которых согласно технологическому процессу необходимо определенное время. Далее необходимо сформировать партии запуска деталей и сроки с учетом опережения, чтобы к моменту сборки узла, все детали, из которых он состоит, были уже готовы. Согласно технологическому маршруту изготовления деталей и узлов необходимо сформировать расписания работы участков на сутки, смены, часы.

>> содержание

Методы моделирования

Моделирование возможно с использованием следующих методов:

     - Имитационные модели;

     - Математическое моделирование;

     - Теория графов и сетей;

     - Теория массового обслуживания;

     - Объектно-ориентированный подход;

     - Теория расписаний.

Имитационные модели

Основными требованиями к имитационным моделям являются адекватность модели, максимальная приближенность алгоритмов к методологии объектного программирования и универсальность, как возможность представления всего множества дискретных состояний системы. Использование в имитационном моделировании сетей Петри, как наиболее универсального и часто встречающегося метода формализации имитационных моделей, в большинстве случаев, ограничено построением несложных циклических моделей с обозримым количеством состояния системы.[5]

При моделировании работы цехов данным образом можно выделить следующие особенности:

     1) за счет свойства масштабирования сети во времени появляется возможность анализа состояния всех объектов на любом разрезе сети;

     2) возможность создания сетей любой сложности и размерности, как функции от времени и количества полюсов сети, представляющих собой ЕП;

     3) возможность моделирования на уже созданной сети в пределах любых интервалов времени, с различных, интересующих проектанта событий;

     4) возможность оценки расписаний работы оборудования;

     5) максимальная приближенность логики синтеза сетей к логике построения программного обеспечения;

     6) возможность использования модульной структуры программного обеспечения процесса моделирования.

Математическое моделирование

Одним из основных требований, предъявляемых к подсистемам оперативно-календарного планирования (ОКП), является точность формируемого расписания работ. Точность любой модели, как правило, зависит от полноты ее представления, адекватности условиям реальной производственной системы. В большинстве моделей ОКП расписание традиционно строилось относительно основного класса обслуживающих устройств. Модель расписания, методика и алгоритм его формирования при выполнении различных партий деталей (так называемых партия-операций) и влияния других технологических факторов представлены в работе.[6]

На множестве номенклатуры деталей, представленном множеством единиц планирования (ЕП), которыми являются партия-операции, М и множеством обслуживающих устройств, необходимо составить оптимальное расписание. Графическая интерпретация произвольной модели расписания для случая представляется диаграммой Ганта. Обобщенная математическая модель для оперативно-календарного планирования, включающая следующие элементы:

     - потери времени, при поступлении новых партий деталей;

     - потери времени, связанные с ожиданием партий деталей, находящихся в требуемый момент на обработке на предыдущей операции;

     - потери времени, связанные с ожиданием партий деталей, находящихся в процессе транспортирования;

     - потери времени, связанные с ожиданием партий деталей, находящихся в процессе транспортирования.

Полученная модель оптимизируется одним из численных методов и получается оптимальное решение на указанном временном интервале. Горизонтом планирования расписания может быть 8-ми часовая смена. Недостатками данного вида моделирования является то, что оперативное планирование, является достаточно сложной динамической системой, математическая модель которой описывается достаточно сложными уравнениями, составление которых невозможно без определенного рода допущений, что сказывается на ее точности.[7]

Теория графов и сетей

Для исследования систем состоящих из разнородных элементов применимым является аппарат теории сетей массового обслуживания (ТСМО). Сеть массового обслуживания представляет собой совокупность систем массового обслуживания, в которой циркулируют заявки, переходя из одной системы в другую. В основе ТСМО лежит сетевое описание технологического процесса обработки изделия. Сеть, при этом отображает взаимосвязи между автономно функционирующими элементами и подсистемами. Сеть представляет собой граф, состоящий из множества узлов и ориентированных дуг, соединяющих узлы. При сетевом представлении структуры цехов узлы выступают как автономные агрегаты или позиции обработки, дуги показывают направление потока заявок (изделий) в системе. В зависимости от поставленной задачи и исследуемой функции изменяется число узлов в сети, их состав и связи между ними.[8]

Теория массового обслуживания

Данные модели основываются на гипотезе, о вероятностном характере протекания процессов и взаимодействия оборудования.[9] При моделировании работы цехов (с помощью аппарата Q-схем), используются допущения:

     - последовательность выполнения операций технологических маршрутов. Технологический маршрут используется только для расчета распределения вероятностей частоты и длительности пребывания изделий на рабочих позициях;

     - производственная система рассматривается как замкнутая система, т.е. в каждый момент времени в ней находится постоянное количество изделий;

     - каждая рабочая позиция имеет накопитель неограниченной емкости.

Объектно-ориентированный подход

Является подклассом имитационных моделей. К наиболее мощным и выразительным моделям представления знаний о дискретных процессах в реальном времени (РВ) относится продукционная система. Однако при описании сложных процессов мониторинга, контроля и управления с использованием большого числа внешних дискретных объектов возникает ряд хорошо известных трудностей. В данное время используется новая объектно-продукционная модель знаний (ОПМЗ), которая является результатом декомпозиции продукционной модели системы реального времени "ПРОДУС" на основе объектно-ориентированного подхода. В ней устранены такие недостатки продукционной модели, как отсутствие средств структуризации и декомпозиции базы правил, механизма реального распараллеливания и повторного использования знаний, а также предложен новый децентрализованный механизм явного управления интерпретацией и синхронизацией параллельных объектов.[10]

Его преимущества по сравнению с традиционным имитационным моделированием можно отнести:

     - простота систематизации и структурирования компонентов;

     - наследование позволяет реализовывать сложные модели с различными модификациями, а значит его можно применять к конкретной системе, без дополнительного перепрограммирования;

     - учет асинхронности и распараллеливания

Теория расписаний

Качество функционирования современного производства во многом определяется решениями, принимаемыми на этапах календарного планирования и оперативного управления. Особенно это актуально в связи с созданием современных автоматизированных производств – гибких производственных систем (ГПС). Системы оперативно – календарного планирования современных производств строятся в том числе и на достижениях так называемой «теории расписаний».

Теория расписаний – это наука, занимающаяся исследованиями детерминированных обслуживающих систем на предмет оптимизации расписаний их функционирования.[11]

Примеры таких систем:

     - цех, участок, на станках которых осуществляется обработка деталей;

     - ВУЗ, где преподаватели обучают студентов и т.д.

Процесс функционирования обслуживающей системы может быть описан путем задания расписания (календарного плана, временного графика и т.п.).

Расписание – некоторая совокупность указаний относительно того, какие именно требования какими именно приборами обслуживаются в каждый момент времени.

Пример. На рисунке 9.1 приведен график расписания Si(t), iєN обслуживания требований N={1,2,3,4} приборами M={1,2,3} при различных маршрутах обслуживания требований. Все длительности обслуживания равны «1».

Рисунок 9.1 – График расписания обслуживания требований N = {1, 2, 3, 4} приборами M = {1, 2, 3}

Методы оптимизации

Если существует несколько допустимых расписаний, то естественно необходимо выбрать лучшее из них.

Оптимальное расписание может быть найдено в результате перебора конечного множества возможных вариантов. Основная трудность при этом состоит в том, что число таких вариантов очень велико и растет, по меньшей мере, экспоненциально с ростом размерности задачи. Известны так называемые эвристические алгоритмы формирования расписаний, алгоритмы на основе методов линейного и динамического программирования. Задачи составления расписаний для некоторых сложных систем обслуживания до сих пор не решены (NP – трудные задачи).

Метод ветвей и границ

Методологическую основу исследования составили положения системного анализа, методы планирования производственной программы предприятия, экономико-математические методы и модели, экспертные методы, методы принятия управленческих решений. Для разработки компьютерной подсистемы оперативного планирования производства в машиностроении выбран муравьиный алгоритм, который дает наиболее хорошие результаты по сравнению с другими инновационными методами, и генетические алгоритмы, адекватно учитывающие основные закономерности производства и реализации продукции на основе процессов естественного отбора.[12]

Метод ветвей и границ — один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.

Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.

Генетические алгоритмы

Одними из современных методов оптимизации, основанных на эвристических алгоритмах, являются генетические алгоритмы.

Генетический алгоритм был получен в процессе обобщения и имитации в искусственных системах таких свойств живой природы, как естественный отбор, приспособляемость к изменяющимся условиям среды, наследование потомками жизненно важных свойств от родителей и т.д. Так как алгоритм в процессе поиска использует некоторую кодировку множества параметров вместо самих параметров, то он может эффективно применяться для решения задач дискретной оптимизации, определённых как на числовых множествах, так и на конечных множествах произвольной природы. Поскольку для работы алгоритма в качестве информации об оптимизируемой функции используются лишь её значения в рассматриваемых точках пространства поиска и не требуется вычислений ни производных, ни каких-либо иных характеристик, то данный алгоритм применим к широкому классу функций, в частности, не имеющих аналитического описания. Использование набора начальных точек позволяет применять для их формирования различные способы, зависящие от специфики решаемой задачи, в том числе возможно задание такого набора непосредственно человеком.[13]

Сила генетических алгоритмов в том, что этот метод очень гибок, и, будучи построенным в предположении, что об окружающей среде нам известен лишь минимум информации (как это часто бывает для сложных технических систем), алгоритм успешно справляется с широким кругом проблем, особенно в тех задачах, где не существует общеизвестных алгоритмов решения или высока степень априорной неопределенности.

Механизм простого ГА (ПГА) несложен. Он копирует последовательности и переставляет их части. Предварительно ГА случайно генерирует популяцию последовательностей - стрингов (хромосом). Затем ГА применяет множество простых операций к начальной популяции и генерирует новые популяции.

ПГА состоит из 3 операторов: репродукция, кроссинговер, мутация.

Репродукция - процесс, в котором хромосомы копируются согласно их целевой функции (ЦФ). Копирование хромосом с «лучшим» значением ЦФ имеет большую вероятность для их попадания в следующую генерацию. Оператор репродукции (ОР), является искусственной версией натуральной селекции, «выживания сильнейших» по Дарвину.

После выполнения ОР оператор кроссинговера (ОК) может выполниться в несколько шагов. На первом шаге выбираются члены нового репродуцированного множества хромосом. Далее каждая пара хромосом (стрингов) пересекается по следующему правилу: целая позиция k вдоль стринга выбирается случайно между 1 и длиной хромосомы минус единицу т.е. в интервале (1,L-1). Длина L хромосомы это число значащих цифр в его двоичном коде. Число k, выбранное случайно между первым и последним членами, называется точкой ОК или разделяющим знаком.

Механизм ОР и ОК включает случайную генерацию чисел, копирование хромосом и частичный обмен информацией между хромосомами.

Генерация ГА начинается с репродукции. Мы выбираем хромосомы для следующей генерации, вращая колесо рулетки, такое количество раз, которое соответствует мощности начальной популяции. Величину отношения Fi(x)/SumF(x) называют вероятностью выбора копий (хромосом) при ОР и обозначают Pi(OP). Здесь Fi(x) - значение ЦФ i-той хромосомы в популяции, SumF(x) - суммарное значение ЦФ всех хромосом в популяции. Величину Pi(OP) также называют нормализованной величиной. Ожидаемое число копий i-ой хромосомы после ОР определяют N=Pi(OP)*n. Здесь n - число анализируемых хромосом.

Число копий хромосомы, переходящее в следующее положение, иногда определяют на основе выражения: Ai=Fi(x)/СреднееFi(x).

Во многих проблемах имеются специальные знания, позволяющие построить аппроксимационную модель. При использовании ГА это может уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.

Муравьиный алгоритм

Оптимизация в магистерской работе будет производится, в основном, с помощью муравьиных алгоритмов. Поэтому, наиболее подробно я остановлюсь именно на них.

Основная идея данного алгоритма является моделирование поведения муравьев, коллективной адаптации. Колония представляет собой систему с очень простыми правилами автономного поведения особей. Однако, несмотря на примитивность поведения каждого отдельного муравья, поведение всей колонии оказывается достаточно разумным. Таким образом, основой поведения муравьиной колонии служит низкоуровневое взаимодействие, благодаря которому, в целом, колония представляет собой разумную многоагентную систему. Взаимодействие определяется через химическое вещество – феромона, откладываемого муравьями на пройденном пути. При выборе направления движения муравей исходит не только из желания пройти кратчайший путь, но и из опыта других муравьев, информацию о котором получаем через уровень феромонов ребрах. С течением времени происходит процесс испарения феромонов, которое является отрицательной обратной связью.[14]

Свойства муравья

Каждый муравей обладает собственной «памятью», в которой будет храниться список городов , которые необходимо посетить муравью k, который находится в городе i.

Муравьи обладают «зрением», обратно пропорциональный длине ребра: .

Каждый муравей способен улавливать след феромона, которое будет определять желание муравья пройти по данному ребру. Уровень феромона в момент времени t на ребре будет соответствовать .

Вероятность перехода муравья из вершины i в вершину j будет определяться следующим соотношением:

(9.1)

где – эмпирические коэффициенты.
Нетрудно заметить, что данное выражение имеет эффект «колеса рулетки».

Количество откладываемого феромона:

(9.2)

где – параметр, имеющий значение порядка длины оптимального пути, – длина маршрута .

Испарение феромона определяется следующим выражением:

(9.3)

где m – количество муравьев, p – коэффициент испарения (p=[0..1]).

Модификации муравьиного алгоритма

«Элитные» муравьи

Элитой называются муравьи, чьи маршруты лучше остальных.
Разработана следующая модификация, основанная на знаниях об «элитных» муравьях. Данная модификация не учитывает количества элитных муравьев. Выражение (9.2) для элиты принимает вид:

(9.4)

где – «авторитет» элитных муравьев. Таким образом, мы можем регулировать влияние «элитных» муравьев с помощью коэффициента . Оптимальное значение , в основном, будет зависеть от размерности графа, численности колонии, времени жизни. Его значение во многом определяет скорость сходимости. Это очень важно, поскольку в реальных ситуациях чаще всего приходится балансировать между качеством решения и временем работы.

Начальное расположение колонии

В простом МА принято считать, что в каждой вершине изначально находится по одному муравью. В данной работе представлены следующие стратегии начального расположения:

«Одеяло» – реализация стандартного размещения муравьев, в каждой вершине находиться по одному муравью. Тогда сложность данного алгоритма выражается следующей зависимостью – , поскольку n=m;

«Дробовик» – случайное распределение муравьев на вершины графа, причем необязательно, чтобы численности колонии и вершин совпадали;

«Фокусировка» – вся колония находится в одной вершине;

«Блуждающая колония» – в каждый момент времени, т.е. на каждой итерации, вся колония перемещается в случайно выбранную вершину.

Отметим, что названия первых трех заимствованы из названий стратегий формирования начальной популяции в генетических алгоритмах (ГА), также относящихся к классу алгоритмов «природных вычислений». В ходе проделанных экспериментальных исследований было выяснено, что сходимость МА и качество решения сильно зависят от начального расположения колонии.

Пример работы муравьиного алгоритма

Рассмотрим случай, показанный на рисунке, когда на оптимальном доселе пути возникает преграда. В этом случае необходимо определение нового оптимального пути. Дойдя до преграды, муравьи с равной вероятностью будут обходить её справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако, те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащён феромоном. Поскольку движение муравьёв определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном до тех пор, пока этот путь по какой-либо причине не станет недоступен.

Рисунок 9.2 - Концепция мурвьиных алгоритмов
(анимация: объем - 102 Кб; размер 707х303; количесвто циклов повторения - бесконечный цикл повторения)

>> содержание

В результате анализа существующих систем планирования выявлены следующие недостатки:

     - разработанные модели не позволяют учитывать многие факторы, влияющие на ход производства, которые для разных предприятий могут быть индивидуальны;

     - использование только математических методов ограничивается невозможностью быстрого реагирования на возникающие ситуации, требующие немедленной корректировки планов.

Для исключения недостатков подобных разработок необходимо использовать эволюционные методы, которые позволили бы получать оптимальные решения проблем реальных производственных ситуаций за малое время. При решении такие методы рассматривают систему планирования как чёрный ящик, когда на входе задаются различные значения параметров планирования, после чего оценивается эффективность получаемых расписаний с точки зрения ключевых показателей эффективности.

На основе анализа существующих разработок в области эволюционных методов перспективным решением сложных комбинаторных задач оптимизации является гибридное использование генетического и муравьиного алгоритмов. Это позволит существенно улучшить систему оперативного планирования, тем самым сократив время получения оптимальных или приемлемых производственных расписаний. Также при появлении случайных событий, влияющих на процесс производства, позволит быстро реагировать на изменение и внесение корректив в исходные данные.

Выходя из того, что динамичность производства, отклонения различного рода, неоднозначно определенные критерии оптимизации, а также большая размерность решаемых задач и малая устойчивость исходной информации – все это вызывает необходимость построения таких методов решения, которые удовлетворяли бы следующим основным требованиям:

     - универсальность, т.е. пригодность к разным типам производства

     - возможность учета разнообразных производственных ограничений

     - переход от одного критерия оптимизации к другому

     - допустимое время счета

     - получение достаточно близкого к оптимальному решения и его оценка

     - обеспечение документацией, содержащей необходимую нормативную и учетную информацию

     - получение реально выполнимых сменных заданий, увязанных с вопросами стимулирования

     - проверка сменных заданий и обеспеченности необходимыми ресурсами

     - возможность внесения изменений в решение на основе учета реального выполнения заданий и корректировка план-графика

     - удобство и релевантность представления исходных данных и результатов решения

Всем перечисленным требования удовлетворяют методы имитационного моделирования. Кроме того, процесс разработки аналитической модели производства чрезвычайно сложен, а в большинстве случаев получить модель просто невозможно. Проведение экспериментов на реальной модели также неприемлемо. Поэтому в качестве основного средства получения параметров производственных систем решено использовать имитационные методы.

Как оптимизационный аппарат для решения задачи выполнения заказов точно в срок, необходимо использовать генетический алгоритм.

Этот метод очень гибок, и, будучи построенным в предположении, что об окружающей среде нам известен лишь минимум информации (как это часто бывает для сложных технических систем), алгоритм успешно справляется с широким кругом проблем, особенно в тех задачах, где не существует общеизвестных алгоритмов решения или высока степень априорной неопределенности.

Во многих проблемах имеются специальные знания, позволяющие построить аппроксимационную модель. При использовании ГА это может уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.

Для оптимизации непосредственно производственных заданий цехам и участкам необходимо использовать, все чаще используемы для оптимизационных задач, муравьиный алгоритм.

Муравьиные алгоритмы представляют собой новый перспективный метод решения задач оптимизации, в основе которого лежит моделирование поведения колонии муравьев. Колония представляет собой систему с очень простыми правилами автономного поведения особей. Однако, несмотря на примитивность поведения каждого отдельного муравья, поведение всей колонии оказывается достаточно разумным. Эти принципы проверены временем - удачная адаптация к окружающему миру на протяжении миллионов лет означает, что природа выработала очень удачный механизм поведения.

Таким образом, оперативно-календарное планирование, которое составляет основу оперативного управления предприятием, очень трудоемкая задача. Ее решение имеет важное значение для работы всего предприятия. В традиционном подходе решения присутствуют существенные недостатки, поэтому в результате работы планируется получить новые методы, которые будут основываться на системах искусственного интеллекта, которые позволяют создавать более гибкие модели, чем методы статистической обработки информации.

>> содержание

В ходе выполнения данного курсового проекта были выполнены задачи по анализу методов и моделей оптимизации, программных средств и готовых программных продуктов оперативного планирования производства в машиностроении.

Произведен анализ существующих систем и подсистем, в заключении которого обоснована актуальность создания подсистемы оперативного планирования производства в машиностроении.

Результатом анализа стали предложения по структуре магистерской работы, результаты выполнения которой смогут быть использованы для оптимизации оперативного планирования производства в машиностроении.

В работе проведен анализ, выявлены положительные и отрицательные стороны существующих методов моделирования, моделей и алгоритмов оптимизации. Приведены весомые аргументы при выборе алгоритмов оптимизации.

Анализ показал, что наиболее подходящим является использование генетического алгоритма и муравьиного алгоритма на разных уровнях оптимизации.

Целью разрабатываемой подсистемы является повышение эффективности работы машиностроительных предприятий за счет составления оптимальных планов производства и нагрузки оборудования.

>> содержание

1. Планирование дискретного производства в условиях АСУ / [Шкурба В.В., Болдырева В.А., Вьюн А.Ф. и др.]. - К. : Техника, 1975. - 296 с.

2. Сачко Н.С. Организация и оперативное управление машиностроительным производством / Н.С. Сачко. - Минск. : Новое знание, 2005. - 635 с.

3. Михайлова Л.В. Формирование и оперативное управление производственными системами на базе поточно-группового производства в автоматизированном режиме / Л.В. Михайлова, Ф.И. Парамонов, А.В. Чудин. - М. : ИТЦ МАТИ, 2002. - 60 с.

4. Сытник В.Ф. АСУП и оптимальное планирование / В.Ф. Сытник. - К. : Вища школа, 1977. - 312 с.

5. Крушевский А.В. Справочник по экономико-математическим моделям и методам / А.В. Крушевский. – К. : Техника, 1982. – 208 с.

6. Первозванский А.А. Математические модели в управлении производством / А.А. Первозванский. - М.: Наука, 1975. – 616 с.

7. Загидуллин Р.Р. Комплексная математическая модель оперативно-календарного планирования в гибких комплексах механической обработки / P.P. Загидуллин // Автоматизация и современные технологии. - 1999. - № 9. - С. 32-24.

8. Введение в теорию графов [Электронный ресурс] / Уилсон Р. - Режим доступа: http://engenegr.ru/2007/05/10/vvedenie_v_teoriju_grafov.html

9. Імітаційне моделювання систем масового обслуговування [Электронный ресурс] / Ю.В. Жерновий. - Режим доступа: http://zyurvas.narod.ru/bibTMO.html

10. Объектно-ориентированное моделирование [Электронный ресурс] / С.С. Гайсарян. - Режим доступа: http://www.citforum.ru/programming/oop_rsis/glava2.shtml

11. Танаев В.С. Введение в теорию расписаний / В.С. Танаев, В.В. Шкурба. - М. : Наука, 1975.

12. Описание метода ветвей и границ [Электронный ресурс]. - Режим доступа: http://math.nsc.ru/AP/benchmarks/UFLP/uflp_bb.html

13. Гладков Л.А. Генетические алгоритмы / Л.А. Гладков, В.М. Курейчик, В.В.Курейчик. – Ростов-на-Дону : Ростиздат, 2004г.

14. Муравьиные алгоритмы [Электронный ресурс] / А.А. Кажаров, В.М.Курейчик. - Режим доступа: http://raai.org/cai-08/files/cai-08_paper_144.doc

>> содержание

При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2009 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

>> содержание